package main

import (
	"math"
)

var (
	dx = []int{1, 0, 0, -1}
	dy = []int{0, 1, -1, 0}
)

func updateMatrix(mat [][]int) [][]int {
	//搜0
	//距离矩阵
	dist := make([][]int, len(mat))
	//搜索队列
	queue := [][]int{}
	seen := make([][]bool, len(mat))
	for i := 0; i < len(mat); i++ {
		di := make([]int, len(mat[0]))
		si := make([]bool, len(mat[0]))
		for j := 0; j < len(mat[0]); j++ {
			si[j] = false
			if mat[i][j] == 0 {
				di[j] = 0
				queue = append(queue, []int{i, j})
			} else {
				di[j] = math.MaxInt32
			}
		}
		dist[i] = di
		seen[i] = si
	}
	//广度优先搜索BFS
	for i := 0; i < len(queue); i++ {
		cell := queue[i]
		for j := 0; j < 4; j++ {
			y, x := cell[0]-dy[j], cell[1]-dx[j]
			//检查坐标边界条件
			if x >= 0 && y >= 0 && x < len(mat[0]) && y < len(mat) && !seen[y][x] {
				seen[y][x] = true
				if mat[y][x] != 0 {
					if dist[y][x] > dist[cell[0]][cell[1]]+1 {
						dist[y][x] = dist[cell[0]][cell[1]] + 1
					}
					queue = append(queue, []int{y, x})
				}
			}
		}
	}
	return dist
}

func main() {
	mat := make([][]int, 20)
	mat[0] = []int{1, 1, 1}
	mat[1] = []int{1, 1, 1}
	mat[2] = []int{1, 1, 1}
	mat[3] = []int{1, 1, 1}
	mat[4] = []int{1, 1, 1}
	mat[5] = []int{1, 1, 1}
	mat[6] = []int{1, 1, 1}
	mat[7] = []int{1, 1, 1}
	mat[8] = []int{1, 1, 1}
	mat[9] = []int{1, 1, 1}
	mat[10] = []int{1, 1, 1}
	mat[11] = []int{1, 1, 1}
	mat[12] = []int{1, 1, 1}
	mat[13] = []int{1, 1, 1}
	mat[14] = []int{1, 1, 1}
	mat[15] = []int{1, 1, 1}
	mat[16] = []int{1, 1, 1}
	mat[17] = []int{1, 1, 1}
	mat[18] = []int{1, 1, 1}
	mat[19] = []int{0, 0, 0}
	matrix := updateMatrix(mat)
	for i := 0; i < len(matrix); i++ {
		print("[")
		for j := 0; j < len(matrix[0]); j++ {
			print(matrix[i][j])
		}
		println("]")
	}
}
